1. Field of the Invention
The present invention relates to a digital-signal processing apparatus, a digital-signal processing method, a program, and an authentication apparatus. The invention is suitable for performing, for example, fast Fourier transform (FFT).
2. Description of the Related Art
Fast Fourier transform (hereinafter called FFT) is an algorithm that employs bit inversion or butterfly operation, as well as complex multiplication, thereby increasing the speed of discrete Fourier transform (DFT).
To perform discrete Fourier transform on, for example, n data items, complex multiplication must be carried out n2 times in most cases. If fast Fourier transform is performed on the same number of items, it suffices to perform complex multiplication only n log2n times. The reduction in the number of times the complex multiplication is repeated results in a tremendous decrease in time required. A computer that can make 109 operations per second requires 30 years to perform discrete Fourier transform on 230 data items. It requires only three minutes to perform fast Fourier transform on 230 data items.
FFT can thus remarkably reduce the amount of data that should be processed to perform the discrete Fourier transform. The greater the number of data items subjected to operation, the more prominent the advantage of FFT.
Discrete Fourier transform can realize convolution in the Fourier space. This is because the result of convolution of two functions f(x) and g(x) is equal to the product of the functions f(x) and g(x) that have been subjected to the discrete Fourier transform. In practice, the functions f(x) and g(x) are first subjected to discrete Fourier transform, and the product of the functions thus operated is then subjected to inverse discrete Fourier transform. The result of the convolution is thereby obtained.
Accordingly, FFT is generally employed in various types of data processing. It is applied to, for example, the process of determining data components (frequency-component analysis), the process of synthesizing given components of specific data (waveform synthesis), and the process of extracting desired components from data (digital filtering). (See PCT National Publication No. 2003-509748.)